package heap.heapSort;

import sortingAdvance.quickSort.SortTestHelper;

/**
 * 快速排序
 * mxf
 * 2018年5月25日13:55:34
 */
public class QuickSort {

    public static void sort(Comparable[] arr){
        int length = arr.length;
        sort(arr, 0, length - 1);
    }

    private static void sort(Comparable[] arr, int l, int r) {
        if(l >= r) {
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    private static int partition (Comparable[] arr, int l, int r) {
        Comparable v = arr[l];
        int j = l;
        for(int i = l + 1; i <= r; i++) {
            if(v.compareTo(arr[i]) > 0) {
                j ++;
                swap(arr, j, i);
            }
        }
        swap(arr, j, l);
        return j;
    }

    private static void swap(Comparable[] arr, int l, int r) {
        Comparable v = arr[l];
        arr[l] = arr[r];
        arr[r] = v;
    }

    public static void main(String[] args) {
        Integer[] arr = SortTestHelper.generateRandomArray(100, 0, 100);
        QuickSort.sort(arr);
        SortTestHelper.printArray(arr);
    }
}
